Veremos que la complejidad del algoritmo es $O(k * n^3)$.

Divideremos el análisis en las diferentes partes que componen el algoritmo. Probaremos que las complejidades son las siguientes: \\
- Crear el grafo: $O(n^2)$
- Conectar los nodos: $O(max(k*n^2, n^3))$
- Encontrar el camino mínimo: $O(k * n^3)$
- Traceback para devolver el camino minimo: $O(k * n^2)$

De modo que la complejidad total, que es la suma de esas complejidades resultara ser $O(k * n^3)$.

Comenzamos analizando la complejidad para crear el grafo:

\begin{quote}
\begin{verbatim}
	crearGrafo(nodes:vector<Node*>, cols:int, rows:int)
		nodes.resize(cols*rows);
    		for (int row = 0; row < rows; row++) {
	    		for(int col = 0; col < cols; col++) {
        				nodes[col+row*cols] = new Node(row, col, 0);
        			}
    		}
\end{verbatim}
\end{quote}

Se comienza haciendo un resize de $nodes$, que es un vector de STL y el resize de n elementos toma O(n). Por lo que resize(cols*rows) toma O(cols*rows) y como cols = rows = n, luego resize(cols*rows) = resize(n*n) que tiene coste $O(n^2)$.
Luego se ejecuta un for $rows$ veces con un for anidado que se ejecuta $cols$ veces y como cols = rows = n, nuevamente el coste es $O(n^2)$.
De modo que el coste total de crear un grafo es $O(n^2 + n^2) = O(n^2)$.

Ahora veremos que la complejidad de conectar los nodos es $O(max(k*n^2, n^3))$.\\
La implementación para conectar los nodos es la siguiente:

\begin{quote}
\begin{verbatim}

	conectarNodos(map:Array*, graph:Graph*, cols:int, rows:int, k:int) : void {
		for(int row=0; row<graph->rows; row++) { // O(n)
       	 		for(int col=0; col<graph->cols; col++) { // O(n)
            			Node* node = graph->getNode(row, col); // O(1)
				conectarNodo(map, graph, node, col, row, ks) // O(n+k)      
			}     	
        		}   	
	}
	
	conectarNodo(map:Array*, graph:Graph*, node:Node*, col:int, row:int, k:int) : void {
		if (map != NULL) {
            	    	node->jumpPower = map[(col+row*graph->cols)]; // O(1), acceso array
            	} else {
               	 	node->jumpPower = rand() \% graph->cols + 1; // O(1)
            	}
            
           	for(int jumpPower=1; jumpPower<=node->jumpPower+k; jumpPower++) { 
                		int powerUsed = jumpPower > node->jumpPower ? 
				node->jumpPower : jumpPower;
                		int kUsed = jumpPower > node->jumpPower ? 
				jumpPower - node->jumpPower : 0;
                		if(col < graph->cols-jumpPower) {
                    		graph->connect(node, graph->getNode(row, col+jumpPower), 
					powerUsed, kUsed); // O(1)
                		}
                		if(col >= jumpPower) {
                    		graph->connect(node, graph->getNode(row, col-jumpPower), 
					powerUsed, kUsed);
                		}
                		if(row < graph->rows-jumpPower) {
                   	 	graph->connect(node, graph->getNode(row+jumpPower, col), 
					powerUsed, kUsed);
                		}
                		if(row >= jumpPower) {
                    		graph->connect(node, graph->getNode(row-jumpPower, col), 
					powerUsed, kUsed);
                		}
            	}
	}
\end{verbatim}
\end{quote}

$conectarNodo$ ejecuta un bucle que se ejecuta a lo sumo node->jumpPower + k(o sea máximo salto posible desde un nodo). Como la potencia de salto de un nodo puede ser a lo sumo n, luego se puede acotar la cantidad de iteraciones de este ciclo por n+k. Dentro de el ciclo se hace la conexión de los nodos, y hacer una conexión es $O(1)$, pues es solo un acceso a un array y una asignación. Como $conectarNodos$ ejecuta $conectarNodo$ $n^2$ veces, luego la complejidad total es $O(n^2 * (k+n)) = O(n^2 * k + n^3)$. Como no hay una relación entre k y n, no es posible definir cual de los dos sumandos es menor, luego la complejidad resulta $O(max(n^2 * k, n^3))$.

Ahora veamos que la complejidad de encontrar el camino mínimo es $O(n^3 * k)$.
La implementación para encontrar el camino mínimo es la siguiente:

\begin{quote}
\begin{verbatim}
void Dijkstra::findPath(Node* fromNode, Node* toNode) {
    unvisited.push(new UnvisitedNode(fromNode, 0, k)); // O(1)
    
    while (unvisited.size() > 0) { // O(k * n^2)
        UnvisitedNode* unvisitedNode = unvisited.top(); // O(1)
                       
        Node* node = unvisitedNode->node;
        int jumpsSoFar = unvisitedNode->jumpsSoFar;
        int kLeft = unvisitedNode->kLeft;
        
        delete unvisitedNode;
        
        if (node == toNode) {
            break;
        }
        
        unvisited.pop(); // O(log(k * n^2))
        

        for (int i=0; i<node->edgesToNextNodes.size(); i++) { // O(4*k)
            Arrow* edgeToNextNode = node->edgesToNextNodes[i];
            Node* nextNode = edgeToNextNode->toNode;
            int kUsed = edgeToNextNode->kUsed;
            int powerUsed = edgeToNextNode->powerUsed;
            int nextNodeKLeft = kLeft - kUsed;
            if(jumpsSoFar + 1 < nextNode->minJumps && nextNodeKLeft >= 0) {
                // como siempre saco los nodos por la minima cantidad de saltos, solo va a pasar
                // una vez que la minima cantidad de saltos + 1 sea menor a la del nodo siguiente
                nextNode->minJumps = jumpsSoFar + 1;
                nextNode->maxKLeftSoFar = nextNodeKLeft;
                nextNode->jumpsSoFar[nextNodeKLeft] = nextNode->minJumps;
                nextNode->prevNodes[nextNodeKLeft]->toNode = node;
                nextNode->prevNodes[nextNodeKLeft]->powerUsed = powerUsed;
                nextNode->prevNodes[nextNodeKLeft]->kUsed = kUsed;
                unvisited.push(new UnvisitedNode(nextNode, jumpsSoFar+1, 
                		nextNodeKLeft));
            } else if(nextNode->maxKLeftSoFar < nextNodeKLeft && nextNodeKLeft >= 0) {
                nextNode->maxKLeftSoFar = nextNodeKLeft;
                nextNode->jumpsSoFar[nextNodeKLeft] = jumpsSoFar + 1;                
                nextNode->prevNodes[nextNodeKLeft]->toNode = node;
                nextNode->prevNodes[nextNodeKLeft]->powerUsed = powerUsed;
                nextNode->prevNodes[nextNodeKLeft]->kUsed = kUsed;
                unvisited.push(new UnvisitedNode(nextNode, jumpsSoFar+1, 
                		nextNodeKLeft));
            }
        }
    }
}
\end{verbatim}
\end{quote}

Analizaremos la complejidad del ciclo principal.
Lo peor que puede pasar es que unvisited tenga el mayor tamaño posible.
Un análisis del problema, da como resultado que $|unvisited| <= (k+1) * n^2$, veamos por que:

En cada iteración se toma un nodo v de unvisited y se lo "expande", agregando a unvisited los nodos alcanzables desde v que aun no fueron visitados.
Sea un nodo w, para considerarlo como no visitado, se evalúa si la cantidad de saltos con que se puede llegar desde v es menor a la cantidad de saltos con que se ha llegado hasta el momento a w. O sino, en caso de que la cantidad de saltos no sea menor, se evalúa si desde v se puede llegar a w con mas $kLeft$ que con el que se ha llegado hasta ahora a w.
De modo que como se puede llegar a los nodos con $0 <= kLeft <= k$,  solo se puede agregar cada nodo $k+1$ veces. Luego como hay $n^2$ nodos, resulta que $|unvisited| <= (k+1) * n^2$.
Aquí haremos una aclaración que nos va a resultar útil para un análisis posterior. Dijimos que se puede llegar a los nodos con $0 <= kLeft <= k$, y también es cierto que como en una fila o columna solo hay n nodos, luego el máximo k que podemos necesitar usar para llegar a los nodos es n-2, pues la potencia mínima de un casillero es 1. Entonces también vale que $0 <= kLeft <= n-2$ y que por consiguiente, $|unvisited| <= (n-2) * n^2 <= n^3$. 
Nota: queremos hacer incapié en que no estamos diciendo que el k está acotado por n, sino que respecto a cada nodo, el k máximo necesario para saltar a los demás es n-2, lo cual se usa para calcular |unvisited|.

Luego, como dentro de cada iteración hay un ciclo que recorre los nodos adyacentes de cada nodo y agrega los nodos no visitados a $unvisited$. Como un nodo puede ser adyacente a todos los nodos en su fila y columna(si $p+k >= n$), este ciclo puede tener hasta (n-1) * 2 iteraciones, pues hay n-1 nodos además del nodo considerado en su fila y columna. 
Agregar un nodo a $unvisited$, tiene complejidad igual a $log(|unvisited|)$, pues $unvisited$ es una cola con prioridad basada en heap, y la complejidad da la documentación de STL es que es el logaritmo de la longitud de la cola.
Luego la complejidad del ciclo interno resulta $O(2 * (n-1) * log(n^2 * (k+1))$. Pero como el ciclo interno se puede ejecutar a lo sumo $(k+1) * n^2$ veces, entonces resulta que no se esta cumpliendo con la complejidad buscada que es $O(n^3 * k)$. 
Haciendo un mejor análisis, se puede observar que el costo de agregar los nodos a $unvisited$ está amortizado. Para esto basta con ver que el ciclo princical se ejecuta a lo sumo $n^2 * (k+1)$ veces, lo que es igual al tamaño máximo de $unvisited$. Por ende, para dar sentido a la amortización se puede ver como si las inserciones a $unvisited$ estuviesen distribuidas entre todas las iteraciones del ciclo principal y como si en cada iteración solo se insertase un elemento a $unvisited$. O sea que de forma amortizada solo hay una inserción a $unvisited$ en cada iteración. 
Luego se puede calcular el coste del ciclo como O(2 * (n-1)) = O(n), sacando del calculo de la complejidad el coste de las inserciones y sumándoselo. De modo que la complejidad del ciclo interno resulta $O(n + log(n^2 * k))$. 

Por último, en cada iteración del ciclo principal se remueve un elemento, lo que toma $log(n^2 * k)$, pues según la documentacion de STL, remover un elemento de la cola de prioridad basada en heap también toma logaritmo de la longitud de la cola.

Entonces, para concluir, la complejidad del ciclo principal es:\\

\begin{quote}
$O(|unvisited| * (iteraciones\_ciclo\_interno + remover\_nodo + insertar\_nodo)) =$ \\
$O(n^2 * k * (n + log(|unvisited|) + log(|unvisited|))) = $\\
$O(n^2 * k * (n + log(n^2 * k) + log(n^2 * k))) = $\\
$O(n^2 * k *(n + 2 (2*log(n) + log(k)))) = $\\
$O(n^3 * k  + n^2 * k * log(n) + n^2 * k * log(k)) = $\\
$O(n^3 * k  + n^2 * k * log(k)) $\\
\end{quote}

Llegado a este punto, es necesario probar que log(k) < n. Previamente aclaramos que $|unvisited| <= n^3$ y luego resulta que $O(log(|unvisited|)$ es igual a $O(log(n^2 * k)$, pero también es igual a $O(log(n^3))$.
Entonces usando ese resultado, replanteamos el cálculo de la complejidad y usamos que $|unvisited| <= n^2 * k$ y que $|unvisited| <= n^3$, según convenga para llegar a la complejidad buscada:\\

\begin{quote}
$O(|unvisited| * (iteraciones\_ciclo\_interno + remover\_nodo + insertar\_nodo)) = $\\
$O(n^2 * k * (n + log(|unvisited|) + log(|unvisited|))) = $\\
$O(n^2 * k * (n + log(n^3) + log(n^3))) = $\\
$O(n^2 * k *(n + 2 (3*log(n) + 3* log(n)))) = $\\
$O(n^3 * k  + n^2 * k * 12 * log(n)) = $\\
$O(n^3 * k  + n^2 * k * log(n)) = $\\
$O(n^3 * k)$\\
\end{quote}

De esa manera llegamos a la complejidad esperada, $O(n^3 * k)$.

Falta probar que el traceback para devolver el camino mínimo tiene complejidad $O(k * n^2)$.
La implementación para hacer el traceback es la siguiente:

\begin{quote}
\begin{verbatim}
traceback(Node* fromNode, Node* toNode, int k) {
    Node* node = toNode;
    // Cargo los valores desde el nodo final saliendo con la menor cantidad de saltos.
    // Desde los otros nodos puede que la cantidad de saltos que use no sea la minima.
    int jumpsCount = node->minJumps;
    int kLeft = k;
    int lastUsedK = 0;
    int lastPowerUsed = 0;
    int totalUsedK = 0;
    
    list<PathNode*> path;
    
    // Recorro hacia atras hasta llegar al nodo inicial
    while(node != NULL && node != fromNode) { // O(n^2), a lo sumo recorro todos los nodos una vez
        Node* previousNode = NULL;
        int iKLeft;
        int kUsed = 0;
        int powerUsed = 0;
        // solo busco entre los nodos que tengan suficiente kLeft
        for(iKLeft = totalUsedK; iKLeft<=k; iKLeft++) { // O(k)
            if(node->jumpsSoFar[iKLeft] == jumpsCount) {
                previousNode = node->prevNodes[iKLeft]->toNode;
                kUsed = node->prevNodes[iKLeft]->kUsed;
                powerUsed = node->prevNodes[iKLeft]->powerUsed;
                break;
            }
        }
        if(previousNode) {
            jumpsCount = node->jumpsSoFar[iKLeft] - 1;
            kLeft -= kUsed;
            totalUsedK += kUsed;
            path->push_front(new PathNode(node, lastPowerUsed, lastUsedK, iKLeft)); // O(1)
                        
            lastUsedK = kUsed;
            lastPowerUsed = powerUsed;
            
            node = previousNode;
            
            if(node == fromNode) {
                path->push_front(new PathNode(node, powerUsed, kUsed, k));
            }
        } else {
            node = NULL;
        }
    }
    
    return path;
}
\end{verbatim}
\end{quote}

El algoritmo recorre los nodos desde el nodo final hacia el nodo inicial(en caso de que haya encontrado un camino, sino toNode es NULL y no hace nada).
Para hacer ese recorrido, usa los punteros a los nodos previos que fueron cargados en cada nodo, usando el algoritmo de búsqueda de caminos mínimos.
Como existe la posibilidad de que se necesite recorrer todos los nodos, entonces resulta que el ciclo principal se ejecutará a lo sumo $n^2$ veces. En cada iteración del ciclo se busca al nodo anterior. Para hacer eso, es necesario recorrer entre todos los nodos previos del nodo, y buscar alguno que sea parte de uno de los posibles caminos mínimos. Para encontrar dicho nodo previo, arrancando desde el nodo final, se busca un nodo previo tal que la cantidad de saltos para llegar a el sea igual a la cantidad de saltos(jumpsCount) requerida para encontrar el camino mínimo. En las siguiente iteración se buscará un nodo previo del nodo encontrado en la primera iteración, tal que la cantidad de saltos para llegar a dicho nodo sea jumpsCount-1. En la iteración i se seguirá el mismo razonamiento, buscando siempre un nodo entre los nodos previos tal que la cantidad de saltos requerida para llegar a el sea jumpsCount-i-1. 
Luego por cada nodo puede llegar a buscar entre todos los nodos previos y puede haber un nodo por cada valor de kLeft, con $0<=kLeft<=k.$ 
Entonces el coste total resulta $O(k * n^2)$.

Hemos probado la complejidad de cada una de las partes que componen el algoritmo. La complejidad total resulta de la suma de las partes, es decir:\\

\begin{quote}
$O(Crear el grafo) + O(Conectar los nodos) + O(Encontrar el camino minimo) + O(Traceback para devolver el camino minimo) =$\\
$= O(n^2) + O(max(k*n^2, n^3)) + O(k * n^3) + O(k * n^2) = $\\
$= O(k * n^3)$\\
\end{quote}
